#include <iostream>
using namespace std;


//Definition for binary tree
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool isBalancedSub(TreeNode *root, int *minDepth, int *maxDepth);

    bool isBalanced(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int minDepth, maxDepth;
        return isBalancedSub(root, &minDepth, &maxDepth);
  
    }
    
    bool isBalancedSub(TreeNode *root, int *minDepth, int *maxDepth){
        if(root == NULL){
            *minDepth = 0;
            *maxDepth = 0;
            return true;
        }
        // left
        int iLeftMinDepth = 0;
        int iLeftMaxDepth = 0;
        bool subRes = true;
        subRes = isBalancedSub(root->left, &iLeftMinDepth, &iLeftMaxDepth);
        if(!subRes){
            return false;
        }
        // right
        int iRightMinDepth = 0;
        int iRightMaxDepth = 0;
        subRes = isBalancedSub(root->right, &iRightMinDepth, &iRightMaxDepth);
        if(!subRes){
            return false;
        }
        // total
        *minDepth = 1 + (iLeftMinDepth<iRightMinDepth? iLeftMinDepth : iRightMinDepth);
        *maxDepth = 1 + (iLeftMaxDepth>iRightMaxDepth? iLeftMaxDepth : iRightMaxDepth);
        if((iRightMaxDepth-iLeftMaxDepth)*(iRightMaxDepth-iLeftMaxDepth) > 1){
            return false;
        }
        return true;
    }

int main(int argc, char **argv){
    
    TreeNode root(1);
    TreeNode level1(2);
    TreeNode level2(3);
    root.right = &level1;
    level1.right = &level2;

    cout<<isBalanced(&root);

    
    return 0;
}